// 给定一个数组nums，要求将所有0移动到末尾，并保持所有的非0数字的相对顺序

// 思路1，冒泡排序，超时
// 冒泡排序的思想就是通过相邻元素的比较和交换，使得较大元素从前面移到后面
// 我们可以利用冒泡排序的思想，将值为0的元素移动到数组末尾

// 复杂度分析
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
function moveZeros(nums) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length - i - 1; j++) {
            if (nums[j] === 0 && nums[j + 1] !== 0) {
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]
            }
        }
    }
}


// 思路2： 快慢指针
// 思路：
// 两个指针，slow， fast，slow指向处理好的非0数字数组的尾部，fast指向当前待处理元素
// 不断向右移动fast，每次移动到非零数，将左右指针对应的数交换，同时将 slow右移
// 此时slow的左侧均为处理好的非零数，而从slow指向的位置开始，fast指针左边为止都为0

// 复杂度分析
// 时间复杂度： O(n)
// 空间复杂度：O(1)
function moveZeros2(nums) {
    let slow = 0
    let fast = 0
    while (fast < nums.length) {
        if (nums[fast] !== 0) {
            [nums[slow], nums[fast]] = [nums[fast], nums[slow]]
            slow += 1
        }
        fast += 1
    }
}

let nums = [0, 1, 0, 3, 12]
moveZeros2(nums)
console.log(nums);